# -*- coding: utf-8 -*-


class HashTable():
    __initial_size = 10000

    def __init__(self, size=None):
        self.__size = size

        if size is None:
            self.__size = HashTable.__initial_size

        self.items = [None] * self.__size
        self.__keys = []

    def count(self):
        return len(self.__keys)

    def set(self, key, value):
        keyIndex = self.count()
        self.__keys.append(key)

        if self.count() > 0.7 * self.__size:
            self.__rehash()

        index = self.__get_index(key)
        item = self.items[index]

        if item is None:
            self.items[index] = [keyIndex, value]
        elif self.__keys[item[0]] == key:
            item[1] = value

    def get(self, key):
        index = self.__get_index(key)
        value = None
        if index is not None and self.items[index] is not None:
            value = self.items[index][1]
        return value

    def get_values(self):
        values = []
        for item in self.items:
            if item is not None:
                values.append(item[1])
        return values

    def get_keys(self):
        return self.__keys

    def get_key(self, index):
        return self.__keys[index]

    def get_key_index(self, key):
        index = self.__get_index(key)
        item = self.items[index]
        return item[0]

    def __get_index(self, key):
        "Used linear probing."
        index = self.__primary_hash(key) % self.__size

        if self.__collision(key, index):
            index = self.__secondary_hash(key) % self.__size

        pos = 0
        while self.__collision(key, index):
            index += 1
            index %= self.__size
            pos += 1

        return index

    def __collision(self, key, index):
        item = self.items[index]
        return (item is not None and self.__keys[item[0]] != key)

    def __get_hash(self, key, pos=0):
        hash = self.__primary_hash(key)
        hash += pos * self.__secondary_hash(key)

        return hash

    def __primary_hash(self, key):
        "Used FNV hash function"
        key = str(key)
        h = 2166136261

        for letter in key:
            h = (h * 16777619) ^ ord(letter)

        return h

    def __secondary_hash(self, key):
        "Shift-Add-XOR hash function"
        key = str(key)
        h = 0

        for letter in key:
            h ^= (h << 5) + (h >> 2) + ord(letter)

        return h

    def __rehash(self):

        max_capacity = self.__size
        occupied = self.count() * 100 / self.__size

#        print self.count(), 'items of total capacity', max_capacity
#        print 'percentage:', occupied

        olditems = self.items
        factor = 2
        if self.count() < 50000:
            factor = 4
        self.__size = int(factor * self.__size)
        self.items = [None] * self.__size

#        print 'rehashing to', self.__size, 'buckets'

        for item in olditems:
            if item is not None:
                itemKey = self.__keys[item[0]]
                index = self.__get_index(itemKey)
                self.items[index] = item

#        print 'finished rehashing'
#        print '--------------------------'

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, value):
        return self.set(key, value)
